<h2>题目编号 : 101</h2>
<div style="color:#666;font-size:80%;">29 July 2005</div><br />
<div class="problem_content">
<p>If we are presented with the first <var>k</var> terms of a sequence it is impossible to say with certainty the value of the next term, as there are infinitely many polynomial functions that can model the sequence.</p>
<p>As an example, let us consider the sequence of cube numbers. This is defined by the generating function, <br /><var>u</var><img src="" style="display:none;" alt="_(" /><sub><var>n</var></sub><img src="" style="display:none;" alt=")" /> = <var>n</var><img src="" style="display:none;" alt="^(" /><sup>3</sup><img src="" style="display:none;" alt=")" />: 1, 8, 27, 64, 125, 216, ...</p>
<p>Suppose we were only given the first two terms of this sequence. Working on the principle that &quot;simple is best&quot; we should assume a linear relationship and predict the next term to be 15 (common difference 7). Even if we were presented with the first three terms, by the same principle of simplicity, a quadratic relationship should be assumed.</p>
<p>We shall define OP(<var>k</var>, <var>n</var>) to be the <var>n</var><img src="" style="display:none;" alt="^(" /><sup>th</sup><img src="" style="display:none;" alt=")" /> term of the optimum polynomial generating function for the first <var>k</var> terms of a sequence. It should be clear that OP(<var>k</var>, <var>n</var>) will accurately generate the terms of the sequence for <var>n</var> <img src='images/symbol_le.gif' width='10' height='12' alt='&le;' border='0' style='vertical-align:middle;' /> <var>k</var>, and potentially the <i>first incorrect term</i> (FIT) will be OP(<var>k</var>, <var>k</var>+1); in which case we shall call it a <i>bad OP</i> (BOP).</p>
<p>As a basis, if we were only given the first term of sequence, it would be most sensible to assume constancy; that is, for <var>n</var> <img src='images/symbol_ge.gif' width='10' height='12' alt='&ge;' border='0' style='vertical-align:middle;' /> 2, OP(1, <var>n</var>) = <var>u</var><img src="" style="display:none;" alt="_(" /><sub>1</sub><img src="" style="display:none;" alt=")" />.</p>
<p>Hence we obtain the following OPs for the cubic sequence:</p>
<div style='margin-left:50px;'>
<table>
<tr>
<td>OP(1, <var>n</var>) = 1</td>
<td>1, <span style='color:red;'><b>1</b></span>, 1, 1, ...</td>
</tr>
<tr>
<td>OP(2, <var>n</var>) = 7<var>n</var><img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' />6</td>
<td>1, 8, <span style='color:red;'><b>15</b></span>, ...</td>
</tr>
<tr>
<td>OP(3, <var>n</var>) = 6<var>n</var><img src="" style="display:none;" alt="^(" /><sup>2</sup><img src="" style="display:none;" alt=")" /><img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' />11<var>n</var>+6&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</td>
<td>1, 8, 27, <span style='color:red;'><b>58</b></span>, ...</td>
</tr>
<tr>
<td>OP(4, <var>n</var>) = <var>n</var><img src="" style="display:none;" alt="^(" /><sup>3</sup><img src="" style="display:none;" alt=")" /></td>
<td>1, 8, 27, 64, 125, ...</td>
</tr>
</table>
</div>
<p>Clearly no BOPs exist for <var>k</var> <img src='images/symbol_ge.gif' width='10' height='12' alt='&ge;' border='0' style='vertical-align:middle;' /> 4.</p>
<p>By considering the sum of FITs generated by the BOPs (indicated in <span style='color:red;'><b>red</b></span> above), we obtain 1 + 15 + 58 = 74.</p>
<p>Consider the following tenth degree polynomial generating function:</p>
<p style='text-align:center;'><var>u</var><img src="" style="display:none;" alt="_(" /><sub><var>n</var></sub><img src="" style="display:none;" alt=")" /> = 1 <img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' /> <var>n</var> + <var>n</var><img src="" style="display:none;" alt="^(" /><sup>2</sup><img src="" style="display:none;" alt=")" /> <img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' /> <var>n</var><img src="" style="display:none;" alt="^(" /><sup>3</sup><img src="" style="display:none;" alt=")" /> + <var>n</var><img src="" style="display:none;" alt="^(" /><sup>4</sup><img src="" style="display:none;" alt=")" /> <img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' /> <var>n</var><img src="" style="display:none;" alt="^(" /><sup>5</sup><img src="" style="display:none;" alt=")" /> + <var>n</var><img src="" style="display:none;" alt="^(" /><sup>6</sup><img src="" style="display:none;" alt=")" /> <img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' /> <var>n</var><img src="" style="display:none;" alt="^(" /><sup>7</sup><img src="" style="display:none;" alt=")" /> + <var>n</var><img src="" style="display:none;" alt="^(" /><sup>8</sup><img src="" style="display:none;" alt=")" /> <img src='images/symbol_minus.gif' width='9' height='3' alt='&minus;' border='0' style='vertical-align:middle;' /> <var>n</var><img src="" style="display:none;" alt="^(" /><sup>9</sup><img src="" style="display:none;" alt=")" /> + <var>n</var><img src="" style="display:none;" alt="^(" /><sup>10</sup><img src="" style="display:none;" alt=")" /></p>
<p>Find the sum of FITs for the BOPs.</p>

</div><br />
